package demo1;
import java.util.HashMap;
import java.util.*;


public class DynamicPlanningPractise {
    /**
     * 求数组中的最长等差数组子序列
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int longestArithSeqLength(int[] arr) {
        /**
         本题与上一题中求数组中最长斐波那契子序列相同
         本题仅仅设定dp[i]为最长等差子序列的长度是无法推导出状态转移方程
         因为其并未告知公差是多少，故无法得知是哪一个等差子序列
         等差数列 最低需要有三个元素构成
         状态表示：
         dp[i][j]表示以i下标元素与j下标元素为结尾的所有子序列中 最长等差子序列的长度 i<j
         状态转移方程：

         目前存在的问题：数组中的元素并不是唯一确定的，故寻找下标时有点困难
         我们可以尝试把元素+dp值边填表边存入--》无法确定公差，除非可以将公差一并存入
         我们目前就是需要找到距离i最近的k
         边填表 边绑定下标，是可行的 HashMap中的Key值不能重复
         */
        int n = arr.length;
        //将元素与下标一一存入map中
        HashMap<Integer,Integer> map = new HashMap<>();

        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dp[i][j]=2;
        //3 填表
        int ret = 2;
        // for(int j = 2; j < n; j++) {
        //     for(int i = 1; i < j; i++) {
        //         map.put(arr[i-1],i-1);
        //         if(map.containsKey(2*arr[i]-arr[j])) {
        //             int k = map.get(2*arr[i]-arr[j]);
        //             dp[i][j] = k<i ? dp[k][i]+1 : dp[i][j];
        //         }
        //         ret = Math.max(ret,dp[i][j]);
        //     }
        // }
        //可以更改填表顺序，从而减少时间复杂度 从固定j 变为固定 i
        //提升了几十毫秒 因为省去了对map进行更新的操作
        for(int i = 1; i < n; i++) {
            for(int j = n-1; j > i; j--) {
                map.put(arr[i-1],i-1);
                if(map.containsKey(2*arr[i]-arr[j])) {
                    int k = map.get(2*arr[i]-arr[j]);
                    dp[i][j] = k<i ? dp[k][i]+1 : dp[i][j];
                }
                ret = ret<dp[i][j] ? dp[i][j] : ret;
            }
        }
        return ret;
    }
    /**
     * 求数组中的最长等差数组子序列 - 代码优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int longestArithSeqLengthOther(int[] arr) {
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dp[i][j] = 2;
        //3 填表
        int ret = 2;
        for(int i = 1; i < n; i++) {
            for(int j = n-1; j > i; j--) {
                map.put(arr[i-1],i-1);
                if(map.containsKey(2*arr[i]-arr[j])) {
                    int k = map.get(2*arr[i]-arr[j]);
                    dp[i][j] = k<i ? dp[k][i]+1 : dp[i][j];
                }
                ret = Math.max(ret,dp[i][j]);
            }
        }
        //4 返回值
        return ret;
    }

//    public int numberOfArithmeticSlices(int[] nums) {
//        int n = nums.length;
//        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
//        for(int i = 0; i < n; i++) {
//            ArrayList<Integer> arr = new ArrayList<>();
//            arr.add(i);
//            if(map.containsKey(nums[i])) {
//                map.get(nums[i]).add(i);
//            }
//            map.put(nums[i],arr);
//
//        }
//    }

    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        //将<元素,下标数组>绑定存入Map中
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            if(!map.containsKey(nums[i]))
                map.put(nums[i],new ArrayList<Integer>());
            map.get(nums[i]).add(i);
        }
        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化 ->将dp表中的所有元素初始化为0，即是不用做任何操作
        //3 填表
        for(int j = 2; j < n; j++) {
            for(int i = 1; i < j; i++) {
                long tmp = (long)2*nums[i]-nums[j];
                if(map.containsKey(tmp)) {
                    //此时代表该元素存在，故我们获取下标数组，对符合条件的下标进行处理
                    ArrayList<Integer> indexArray = map.get(tmp);
                    for(int k = 0; k < indexArray.size(); k++)
                        if(indexArray.get(k)<i)
                            dp[i][j] += dp[indexArray.get(k)][i]+1;
                }
            }
        }
        //4 返回值
        int ret = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                ret+=dp[i][j];
        return ret;
    }
    /**
     * 回文子串
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int countSubstrings(String s) {
        //预处理，讲s字符串转化为字符数组
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        boolean[][] dp = new boolean[n][n];
        //2 初始化-无需初始化
        //3 填表
        int sum = 0;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {//保证i<=j
                if(i==j) {
                    dp[i][j] = chars[i]==chars[j];
                } else if(i+1==j) {
                    dp[i][j] = chars[i]==chars[j];
                } else {
                    dp[i][j] = chars[i] == chars[j] && dp[i + 1][j - 1];
                }
                if(dp[i][j]) sum++;
            }
        }
        return sum;
    }

}
